package com.fosss.floyd;

import java.util.Arrays;

/**
 * 图
 */
public class Graph {
    //存储顶点
    private char[] vertexs;
    //存储各顶点到其他顶点的距离
    private int[][] distance;
    //存储各顶点的中间顶点的下标
    private int[][] pre;

    /**
     * 构造器
     * @param vertexs
     * @param matrix
     */
    public Graph(char[] vertexs,int[][] matrix){
        this.vertexs=vertexs;
        this.distance=matrix;
        this.pre=new int[vertexs.length][vertexs.length];
        //初始化pre
        /*for (int i = 0; i < vertexs.length;i++) {
            for (int j = 0; j < vertexs.length; j++) {
                pre[i][j]=i;
            }
        }*/
        for(int i=0;i<vertexs.length;i++){
            Arrays.fill(pre[i],i);
        }
    }

    /**
     * 打印
     */
    public  void show(){
        for (int i = 0; i < distance.length; i++) {
            for (int j = 0; j < distance[i].length; j++) {
                System.out.printf("%-7d",distance[i][j]);
            }
            System.out.println();
        }
        System.out.println("=============================");
        for(int i=0;i< pre.length;i++){
            for(int j=0;j<pre[i].length; j++){
                System.out.print(pre[i][j] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 弗洛伊德算法
     */
    public void floydGo(){
        //依次以每一个顶点为中间顶点，中间顶点为i
        for(int k=0;k<vertexs.length;k++){
            //判断i直接到j的距离与i通过k再到j的距离的大小关系，取较小的替代原来的距离
            //然后更新中间顶点为i
            for(int i=0;i<distance.length;i++){
                for(int j=0;j<distance[i].length; j++){
                    int len=distance[i][k]+distance[k][j];//j通过i再到k的距离
                    if(distance[i][j]>len){
                        //更新距离和中间顶点的下标
                        distance[i][j]=len;
                        pre[i][j]=pre[k][j];//pre[k][j]为k到j的中间顶点，如果k是直接到j的，则值为k,如果不是直接到j的，则不为k
                    }
                }
            }
        }
    }

}




















